Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


Vizualizare solutie pentru problema: string

Titlul problemei string
Grupa Grupa B
Problema numarul 2
Runda numarul 12
Solutie oficiala /* Mugurel Ionut Andreica - Bucuresti, ROMANIA */

/*
Time Complexity: O(N*logN)
- using binary tries
*/

#include
#include
#include
#define filein "string.in"
#define fileout "string.out"
#define maxn 500010
#define maxl 19

typedef struct trie { trie *pa,*pb; };

trie *root;
char s[maxn],found[maxl+1],stack[maxl+1],ch;
long i,j,k,m,n,l,memoc=maxn+2*maxl+4+1+28;

void read();
void buildtrie();
void compute();
void print();

int main()
{
read();
buildtrie();
compute();
print();
return 0;
}

void read()
{
FILE *fin=fopen(filein,"r");
fscanf(fin,"%ld%c",&n,&ch);

for (i=0;i {
fscanf(fin,"%c",&ch);
s[i]=ch;
}

s[n]=0;
}

void inserttrie(long start)
{
long i;
trie *aa,*aux;

for (aa=root,i=start;i if (s[i]=='a')
{
if (aa->pa!=NULL)
aa=aa->pa;
else
{
aux=new trie;
aux->pa=NULL;
aux->pb=NULL;
aa->pa=aux;
aa=aux;

memoc+=sizeof(trie);
}
}
else
{
if (aa->pb!=NULL)
aa=aa->pb;
else
{
aux=new trie;
aux->pa=NULL;
aux->pb=NULL;
aa->pb=aux;
aa=aux;

memoc+=sizeof(trie);
}
}
}

void buildtrie()
{
long i;

root=new trie;
root->pa=NULL;
root->pb=NULL;
memoc+=sizeof(trie);

for (i=0;i inserttrie(i);
}

void df(trie *po,long niv)
{
if (po->pa==NULL)
{
l=niv+1;
for (i=0;i found[i]=stack[i];
found[niv]='a';
}
else
if (po->pb==NULL)
{
l=niv+1;
for (i=0;i found[i]=stack[i];
found[niv]='b';
}
else
{
if (niv+2 {
stack[niv]='a';
df(po->pa,niv+1);
}

if (niv+2 {
stack[niv]='b';
df(po->pb,niv+1);
}
}
}

void compute()
{
l=100;
df(root,0);
}

void print()
{
long i;

freopen(fileout,"w",stdout);
printf("%ld\n",l);

for (i=0;i printf("%c",found[i]);

printf("\n");

/*
printf("%ld\n",memoc);
*/
exit(0);
}

Explicatii despre modul de punctare 10 teste * 5 puncte

Download arhiva teste de intrare  

Click aici pentru a va intoarce

© 2002 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com